from typing import Optional
from python.mypackage import ListNode


class Solution:
    """
    方法：将链表分割成两部分，小于x的节点在前，大于等于x的节点在后，并保持原有的相对顺序
         双指针
    
    Args:
        head: Optional[ListNode] - 输入链表的头节点
        x: int - 分割的基准值
        
    Returns:
        Optional[ListNode] - 分割后的新链表头节点
        
    Time: O(n) - 需要遍历整个链表一次，n为链表长度
    
    Space: O(1) - 只使用了常数个额外指针
    """
    def partition(self, head: Optional[ListNode], x: int) -> Optional[ListNode]:
        sml_dummy, big_dummy = ListNode(0), ListNode(0)
        sml, big = sml_dummy, big_dummy
        while head:
            if head.val < x:
                sml.next = head
                sml = sml.next
            else:
                big.next = head
                big = big.next
            head = head.next
        sml.next = big_dummy.next
        big.next = None
        return sml_dummy.next